Algorithms.8

搜索

代码

• 二分查找

思路：每次循环更新最高和最低点，用中间点和目标比较大小

def binary_search(list, num):
    high = len(list)
    low = 0
    mid = (high+low) // 2

    while True:
        mid = (high+low) // 2
        if num > list[mid]:
            low = mid + 1
        elif num < list[mid]:
            high = mid
        else:
            return mid


if __name__ == "__main__":
    l = [2, 4, 6, 7, 8, 9, 11, 15, 18, 21, 31, 64]
    assert binary_search(l, 18) == 8

• 找出旋转排序数组最小值

Suppose an array sorted in ascending order is rotated at some pivot unknown
to you beforehand. (i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).
Find the minimum element. The complexity must be O(logN)
You may assume no duplicate exists in the array.

def find_min_rotate(array):
    high = len(array) - 1
    low = 0

    while low < high:
        mid = (high+low) // 2
        if array[mid] > array[high]:
            low = mid+1
        else:
            high = mid

    return array[low]


if __name__ == "__main__":
    array = [4, 5, 6, 7, 0, 1, 2]
    assert find_min_rotate(array) == 0

• 跳跃搜索

思路：将有序数组分片，逐一搜索

import math


def jump_search(arr, target):
    len_a = len(arr)
    jump = int(math.sqrt(len_a))
    step = 0

    while step*jump < len_a and target > arr[step*jump]:
        step += 1

    distance = min(len_a-1-(step-1)*jump, jump)
    for i in range(distance):
        if target == arr[(step-1)*jump+1+i]:
            return (step-1)*jump+1+i

    return -1


if __name__ == "__main__":
    arr = [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610]
    target = 144

    assert jump_search(arr, target) == 12